package com.frank.leetcode.question_1_5;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/
 * 3. 无重复字符的最长子串
 * 难度: 中等
 * <p>
 * Question :
 * 给定一个字符串，找出不含有重复字符的最长子串的长度。
 * <p>
 * Demo：
 * 给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
 * 给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
 * 给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列  而不是子串。
 * <p>
 * <p>
 * Created by zhy on 2018/5/31.
 */
public class LengthOfLongestSubstring {
    private static Logger LOG = LoggerFactory.getLogger(LengthOfLongestSubstring.class);

    @Test
    public void run() {
        System.out.println(LOG.isDebugEnabled());
        String[] tests = new String[]{"a", "ab", "abb", "aba", "aa", "bba", "abba", "bbtablud", "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCD"};
        int s = 1;
        switch (s) {
            case 1:
                for (String str : tests) {
                    int val = lengthOfLongestSubstring(str);
                    System.out.println("key = " + str + ", val = " + val);
                }
                break;
            case 2:
                int val = lengthOfLongestSubstring(tests[8]);
                System.out.println("key = " + tests[8] + ", val = " + val);
                break;
        }
    }

    /**
     * 将map 转为int 数组提升性能
     *
     * @param str
     * @return
     */
    private int lengthOfLongestSubstring(String str) {
        int max = 0;
        int length = 0;
        int start = 0;
//        HashMap<Character, Integer> map = new HashMap<>(256);
        int[] defChars = new int[256];
        for (int i = 0; i < defChars.length; i++) {
            defChars[i] = -1;
        }
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            length++;
            int index = defChars[c];
            if (index > -1 && index >= start) {
                LOG.debug("i:{}, length : {} ,start :{} ,index:{}, max : {}", i, length, start, index, max);
                length = i - index;
                start = index + 1;
                LOG.debug("length : {} ,start :{} ,index:{}, max : {} \n", length, start, index, max);
//                System.out.println();
            }
            max = length > max ? length : max;
//            map.put(c, i);
            defChars[c] = i;
        }

//        LOG.debug("length : {} ,start :{} , max : {}", length, start, max);
        if (max < length) {
            max = length;
        }
        return max;
    }


    /**
     * 最佳范例
     */
    private int lengthOfLongestSubstringBest(String s) {
        if (s == null || s.length() < 2) {
            return s.length();
        }
        int[] defChars = new int[256];
        for (int i = 0; i < defChars.length; i++) {
            defChars[i] = -1;
        }
        char[] chars = s.toCharArray();
        int left = -1;
        int result = 0;
        for (int i = 0; i < chars.length; i++) {
            left = Math.max(left, defChars[chars[i]]);
            defChars[chars[i]] = i;
            result = Math.max(result, i - left);
        }
        return result;
    }
}